1. Field of the Invention
The present invention relates to a method and apparatus of allocating bandwidth on a bus-based communication system and, more particularly, to a method and apparatus of adding bus grant information to a memory that is used to grant access to a bus.
2. Description of the Related Art
A bus-based communication system is a system that allows a number of communication circuits to exchange signals with each other over a group of shared electrical pathways. For example, the communication circuits on service cards, such as xDSL and other line cards, can be connected to, and communicate over, a bus.
FIG. 1 shows a block diagram that illustrates a conventional bus-based communications system 100. As shown in FIG. 1, system 100 includes a cell bus 110 that has a first bus BUS-A and a pair of first-bus control lines SEL-A0 and SEL-A1. In addition, cell bus 110 also includes a second bus BUS-B, and a pair of second-bus control lines SEL-B0 and SEL-B1. First bus BUS-A utilizes a first group of electrical pathways, such as eight electrical pathways that represent eight bits, while second bus BUS-B utilizes a second group of electrical pathways, such as eight electrical pathways that represent eight bits.
As further shown in the FIG. 1 example, system 100 also includes a number of service cards 112 that are connected to cell bus 110. Each service card 112 is also connected to a number of network devices 114 to receive a number of streams of data cells DS. The data cells DS can have different priority levels such that a data cell DS from one network device 114 is preferred over the data cell DS from another network device 114.
Each service card 112 includes a communication circuit 116 that has a transmit circuit 120 that transmits data cells onto cell bus 110, and a receive circuit 122 that receives data cells from cell bus 110. Communication circuit 116 also includes a logic block 124 that processes the data cells DS.
In operation, when a number of communication circuits 116 are connected to cell bus 110, one of the communication circuits 116 assumes the role of bus master, while the remaining communication circuits 116 assume the roles of bus slaves and communicate over the bus as allowed by the bus master.
The bus master controls the timing of the bus along with access to the bus. For example, the bus master can define transmission periods on bus BUS-A and bus BUS-B, and determine the communication circuit 116 that has permission to use each of the transmission periods on the buses.
FIG. 2 shows a state diagram that illustrates a prior art state machine 200 operating as a bus master. State machine 200 is executed by the logic block 124 of the communication circuit 116 that is the bus master. As shown in FIG. 2, state machine 200 begins at state 210 by determining whether any requests to use bus BUS-B were received during a first request period.
Requests to use bus BUS-B are received during request periods where each communication circuit 116 that wishes to transmit a data cell over bus 110 outputs a request. The requests are output over select lines SEL-A0, SEL-A1, SEL-B0, and SEL-B1 to the bus master. Each request period can be, for example, 12 clock cycles long to support 24 communication circuits 116.
For example, a 1st communication circuit can request bus BUS-B during a first-request clock cycle of a request period on select line SEL-A0 and SEL-A1, while a 13th communication circuit can request bus BUS-B during the first-request clock cycle on select lines SEL-B0 and SEL-B1. In addition, a 2nd communication circuit can request bus BUS-B during a second-request clock cycle on select line SEL-A0 and SEL-A1, while a 14th communication circuit can request bus BUS-B during the second-request clock cycle on select lines SEL-B0 and SEL-B1. Thus, in this example, after 12 clock cycles, each of 24 communications circuits has had a one clock cycle opportunity to request control of bus BUS-B over select lines SEL-A0, SEL-A1, SEL-B0, and SEL-B1.
Each communication circuit 116 outputs a logic value onto the select lines SEL during its assigned clock cycle to indicate whether a request is being made and, if so, the priority level of the request. For example, a logic value of 0-0 can represent a high priority level, while a logic value of 0-1 can represent a medium priority level. In addition, a logic value of 1-0 can represent a low priority level, while a logic value of 1-1 can represent no request.
When requests are received during the first request period, state machine 200 moves to state 212 to define a group of requesting circuits that include the communication circuits 116 that submitted a bus control request during the first request period. For example, state machine 200 can define a group that includes only the communication circuits 116 that requested control of bus BUS-B during the first request period.
Following this, state machine 200 moves to state 214 to grant access to one of the group of requesting communication circuits to transmit in the next transmission period on bus BUS-B. Access is granted by outputting a grant to the requesting communication circuit 116 over the control lines SEL-B0 and SEL-B1. States 212 and 214 can be, for example, eight clock periods long. In addition, an error correction code can be transmitted at the same time on the select lines SEL-A0 and SEL-A1 that are not carrying the grant. Once the grant has been output, state machine 200 moves to state 216 to wait for a predefined period of time. The total time required to complete states 210–216 can be, for example, 26 clock cycles.
After the predefined time has expired, state machine 200 moves to state 218 to determine whether any requests to use bus BUS-A were received during a second request period. In the present example, one clock cycle before state machine 200 moves to state 218, the communication circuit 116 that received control over bus BUS-B, begins transmitting a data cell on bus BUS-B.
As with bus BUS-B, requests to use bus BUS-A are also received during a request period where each communication circuit 116 that wishes to transmit a data cell over bus 110 can output a request. The requests are again output over select lines SEL-A0, SEL-A1, SEL-B0, and SEL-B1 to the bus master, and the request period can also be 12 clock cycles long to support 24 communication circuits 116.
For example, a 1st communication circuit can request bus BUS-A during a first-request clock cycle of a next request period on select lines SEL-B0 and SEL-B1, while a 13th communication circuit can request bus BUS-A during the first-request clock cycle on select lines SEL-A0 and SEL-A1. In addition, a 2nd communication circuit can request bus BUS-A during the second-request clock cycle on select lines SEL-B0 and SEL-B1, while a 14th communication circuit can request bus BUS-A during the second-request clock cycle on select lines SEL-A0 and SEL-A1. Thus, in this example, 12 clock cycles after the request period for bus BUS-A began, each of 24 communications circuits has had a one clock cycle opportunity to request control of bus BUS-A over select lines SEL-A0, SEL-A1, SEL-B0, and SEL-B1.
When requests for bus BUS-A are received during the second request period, state machine 200 moves to state 220 to define a group of requesting circuits that include the communication circuits 116 that submitted a bus control request during the second request period. For example, state machine 200 can define a group that includes only the communication circuits 116 that requested control of bus BUS-A during the second request period.
Following this, state machine 200 moves to state 222 to grant access to one of the group of requesting communication circuits to transmit a data cell in the next transmission period on bus BUS-A. As above, access is granted by outputting a grant to the requesting communication circuit 116 over the control lines SEL-A0 and SEL-A1. States 220 and 222 can be, for example, eight clock periods long. In addition, an error correction code can be transmitted at the same time on the select lines SEL-B0 and SEL-B1 that are not carrying the grant.
Once the grant has been output, state machine 200 moves to state 224 to wait for a predefined period of time. The total time required to complete states 218–224 can be, for example, 26 clock cycles. After the predefined time has expired, state machine 200 returns to state 210 to repeat the process. In addition, if no requests are received during the first request period, state machine 200 waits until the end of the 26 clock cycle, and then moves from state 210 to state 218. Similarly, if no requests are received during the second request period, state machine 200 waits until the end of the 26 clock cycle, and then moves from state 218 to state 210.
Thus, state machine 200 moves through states 210–216, which define a first arbitration period, to determine and grant permission to transmit a data cell during the next transmission period on bus BUS-B, and then through states 218–224, which define a second arbitration period, to determine and grant permission to transmit a data cell during the next transmission period on bus BUS-A. As a result, state machine 200 provides an alternating series of arbitration periods where control over bus BUS-B is determined, and then control over bus BUS-A is determined.
FIG. 3 shows a graphical representation that further illustrates prior art state machine 200. As shown in FIG. 3, state machine 200 defines an alternating series of BUS-B and BUS-A arbitration periods 310 and 312, respectively, on control lines SEL-A0, SEL-A1, SEL-B0, and SEL-B1. The BUS-B arbitration period 310 can be implemented with, for example, states 210–216, while the BUS-A arbitration period 312 can be implemented with, for example, states 218–224.
In the FIG. 3 example, following a BUS-B arbitration period 310, the communication circuit 116 that received the grant begins transmitting a data cell on bus BUS-B one clock cycle before the next BUS-A arbitration period 312, and continues transmitting the data cell for a transmit period. The transmit period can be, for example, 52 clock cycles long.
Similarly, following a BUS-A arbitration period 312, the communication circuit 116 that received the grant begins transmitting a data cell on bus BUS-A one clock cycle before the next BUS-B arbitration period 310, and continues transmitting the data cell for the transmit period.
Thus, as shown in FIG. 3, when a communication circuit 116 receives control over one of the two buses, such as BUS-A, the circuit 116 transmits the data cell over the bus during the next two arbitration periods. By utilizing two 26-cycle arbitration periods and one 52-cycle transmit period, a single 52 byte ATM cell can be transmitted.
FIG. 4 shows a flow chart that illustrates a prior art method 400 of granting access to a bus to one of a number of requesting communication circuits. In the present case, each of the requesting communication circuits submitted a bus control request to the bus master during the same request period.
As shown in FIG. 4, method 400, which can be used to implement steps 214 and 222, begins at step 410 by identifying the requesting communication circuits 116 that wish to transmit a high priority data cell. Priority can be divided into different levels, such as high, medium, and low, and assigned to different data cells DS so that a data cell DS with a high priority is preferred over a data cell DS with a medium or low priority, while a data cell DS with a medium priority is preferred over a data cell DS with a low priority.
If no communication circuits with a high priority data cell requested control, method 400 moves to step 412 to identify the requesting communication circuits 116 that wish to transmit a medium priority data cell. If no communication circuits with a medium priority data cell requested control, method 400 moves to step 414 to identify the requesting communication circuits that wish to transmit a low priority data cell.
Once the requesting communication circuits within a priority level have been identified, method 400 moves from either step 410, step 412, or step 414 to step 416 to determine which of the communication circuits within the priority level will receive the grant (permission to transmit during the next transmission period).
When several requesting communication circuits 116 have the same priority level, the requesting communication circuit 116 to receive the grant can be defined by an arbitration, such as a declining round robin. In a declining round robin, the requesting communication circuits 116 circulate within a hierarchical ranking.
The requesting communication circuit at the top of the ranking is assigned the grant and, after receiving the grant, moves to the bottom of the ranking. The ranking of a communication circuit 116 increases each time the circuit is denied a grant, i.e., control of the bus.
One drawback with method 400 is that if the requesting communication circuits 116 with high priority data streams are over subscribed, method 400 can always or nearly always move from step 410 to step 416. As a result, the higher priority data cells DS can consume all of the available bandwidth, thereby preventing the lower priority data cells DS from being transmitted onto the bus. Thus, there is a need for a method and apparatus that grants access to a bus that insures that lower priority data streams are able to transmit information across the bus.